package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 6072. 转角路径的乘积中最多能有几个尾随零
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/18 9:46
 */
public class MaxTrailingZeros {

    public static void main(String[] args) {
        MaxTrailingZeros test = new MaxTrailingZeros();

//        int[][] arr = {{1,5,2,4,25}};


        int[][] arr = {
                {534, 575, 625, 84, 20, 999, 35},
                {208, 318, 96, 380, 819, 102, 669}
        };

        int i = test.maxTrailingZeros(arr);
        System.out.println(i);
    }


    public int maxTrailingZeros(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] as = new int[m][n + 1];
        int[][] bs = new int[m][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int v = grid[i][j];
                int a = 0;
                int b = 0;
                while (v % 5 == 0) {
                    v /= 5;
                    a++;
                }
                v = grid[i][j];
                while (v % 2 == 0) {
                    v /= 2;
                    b++;
                }
                as[i][j + 1] = as[i][j] + a;
                bs[i][j + 1] = bs[i][j] + b;
            }
        }
        int max = Math.min(as[0][n], bs[0][n]);
        for (int i = 1; i <= n; i++) {
            int a = as[0][i] - as[0][i - 1];
            int b = bs[0][i] - bs[0][i - 1];
            for (int j = 1; j < m; j++) {
                a += as[j][i];
                b += bs[j][i];
                int la = a;
                int lb = b;
                a -= (as[j][i - 1]);
                b -= (bs[j][i - 1]);
                int ra = a + (as[j][n]) - (as[j][i]);
                int rb = b + (bs[j][n]) - (bs[j][i]);
                max = Math.max(max, Math.max(Math.min(la, lb), Math.min(ra, rb)));
            }
        }

        for (int i = 1; i <= n; i++) {
            int a = as[m - 1][i] - as[m - 1][i - 1];
            int b = bs[m - 1][i] - bs[m - 1][i - 1];
            for (int j = m - 2; j >= 0; j--) {
                a += as[j][i];
                b += bs[j][i];
                int la = a;
                int lb = b;
                a -= (as[j][i - 1]);
                b -= (bs[j][i - 1]);
                int ra = a + (as[j][n]) - (as[j][i]);
                int rb = b + (bs[j][n]) - (bs[j][i]);
                max = Math.max(max, Math.max(Math.min(la, lb), Math.min(ra, rb)));
            }
        }
        return max;
    }

}
